/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/copy-books
   @Language: C++
   @Datetime: 19-03-20 11:10
   */

// Method 1, Time O(n*k), 50ms
class Solution {
public:
	/**
	 * @param pages: an array of integers
	 * @param k: An integer
	 * @return: an integer
	 * Tip:
	 * min time must >= max(pages), and <= sum of pages
	 * binary search min time, and check it
	 */
	int copyBooks(vector<int> &pages, int k) {
		// write your code here
		if (pages.size()<1) return 0;
		int max=0, min=0;
		for(int i=0; i<pages.size(); ++i){
			max += pages[i];
			min = (min>pages[i]?min:pages[i]);
		}
		// binary search [min,max]
		while(min<max){
			int mid=min+(max-min)/2, sum=pages[0], part=1;
			for(int i=1; i<pages.size(); ++i){
				sum += pages[i];
				if (sum<=mid) continue;
				if(part<k){
					sum=pages[i];
					++part;
				}
				else{
					min=mid+1;
					break;
				}
			}
			if(sum<=mid) max=mid;
		}
		return min;
	}
};
